package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/29/20 1:51 PM
 *
 *  https://leetcode-cn.com/problems/patching-array/
 */
public class _330_按要求补齐数组 {

    public int minPatches(int[] nums, int n) {


        long limit = 1;
        int index = 0;
        int count = 0;

        while (true) {

            if (limit > n) {

                break;
            }

            if (index < nums.length && nums[index] <= limit) {

                limit += nums[index];
                index++;
            }else {

                count++;
                limit = limit << 1;
            }

        }

        return count;
    }

}
